class Solution {//leetcode139——单词拆分
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> hash;
        for(auto& str:wordDict){
            hash.insert(str);
        }
        int n=s.size();
        vector<bool> dp(n+1,false);
        dp[0]=true;
        s=" "+s;
        for(int i=1;i<=n;i++){
            for(int j=i;j>=1;j--){
                if(dp[j-1]&&hash.count(s.substr(j,i-j+1))){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[n];
    }
};